public class MergeSort {
    public static int[] mergeSort(int[] arr){
        System.out.println("归并排序:");
        int[][] Arr=new int[arr.length][];
        for (int i = 0; i < arr.length; i++) {
            Arr[i]=new int[1];
            Arr[i][0]=arr[i];
        }
        return Sort(Arr)[0];
    }
    public static int[][] Sort(int[][] Arr){
        if (Arr.length==1){
            return Arr;
        }
        int[][] Arr1;
        if (Arr.length%2==1){
            Arr1 = new int[Arr.length/2+1][];
            Arr1[Arr.length/2]=Arr[Arr.length-1];
        }
        else{
            Arr1 = new int[Arr.length/2][];
        }
        for (int i = 0; i < Arr.length-1; i+=2) {
            Arr1[i/2]=new int[Arr[i].length+Arr[i+1].length];
            int j=0,k=0;
            while (j<Arr[i].length || k<Arr[i+1].length){
                if (k==Arr[i+1].length){
                    Arr1[i/2][j+k]=Arr[i][j];
                    j++;
                }
                while (k<Arr[i+1].length){
                    if (j<Arr[i].length&&Arr[i][j]<Arr[i+1][k]){
                        Arr1[i/2][j+k]=Arr[i][j];
                        j++;
                        break;
                    }
                    else{
                        Arr1[i/2][j+k]=Arr[i+1][k];
                        k++;
                    }
                }
            }
        }
        return Sort(Arr1);
    }
}
